/**
 * 默认 a[0] 为已排序数组中的元素，从 arr[1] 开始逐渐往已排序数组中插入元素，从后往前一个个比较，
 * 如果待插入元素小于已排序元素，则已排序元素往后移动一位，直到待插入元素找到合适的位置并插入已排序数组。
 *
 * @param {number[]} arr
 * @returns
 */
function insertionSort(arr: number[]) {
  for (let i = 1, len = arr.length; i < len; i++) {
    const temp = arr[i];
    let preIndex = i - 1;
    while (arr[preIndex] > temp) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex -= 1;
    }
    arr[preIndex + 1] = temp;
  }
  return arr;
}
/**
 * 二分法
 *
 * @param {number[]} arr
 * @param {number} value
 * @returns
 */
function binarySearchOrigin(arr: number[], value: number) {
  let min = 0;
  let max = arr.length - 1;
  while (min <= max) {
    const mid = Math.floor((min + max) / 2); // 折中取整
    if (arr[mid] === value) {
      return mid;
    } else if (arr[mid] > value) {
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }
  return 'NotFound';
}

/**
 * 二分查找，最小值
 *
 * @param {number[]} arr
 * @param {number} maxIndex
 * @param {number} value
 * @returns
 */
function binarySearch(arr: number[], maxIndex: number, value: number) {
  let min = 0;
  let max = maxIndex;
  while (min <= max) {
    const mid = Math.floor((min + max) / 2);
    if (arr[mid] <= value) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }
  return min;
}
